Dynamic Programming
using System;
namespace algorithms.dp
{
public static class CoinChange
{
// ----- Coin Change ---------------------------------------------------
//
// -- min number of coins of denomination d[] to add up S
// -- d[0] = 1
//
// int Make(int[] d, int S)
//
// -- number of ways to add up S with coins of denomination d[]
// -- d[0] = 1
//
// int Count(int[] d, int S)
// ---------------------------------------------------------------------
public static int Make(int[] d, int S)
{
int n = d.Length;
int[] m = new int[S + 1];
for (int s = 1; s <= S; s++)
{
int t = int.MaxValue;
int j = 0;
while (j < n && d[j] <= s)
{
t = Math.Min(m[s - d[j]], t);
j++;
}
m[s] = t + 1;
}
return m[S];
}
public static int Count(int[] d, int S)
{
int n = d.Length;
int[] m = new int[S + 1];
m[0] = 1;
for (int i = 0; i < n; i++)
for (int j = d[i]; j <= S; j++)
m[j] += m[j - d[i]];
return m[S];
}
// ---------------------------------------------------------------------
}
}
using System;
namespace algorithms.dp
{
// ----- Convex Hull Optimization ------------------------------------------
//
// To find minimum ( A[i] * x + B[i] ) for every x.
// -- Lines are added with DESCENDING A.
// -- Minimums are received with ASCENDING X.
//
// ConvexHullOptimization(int maxsize)
// void AddLine(long a, long b)
// long MinValue(long x)
// -------------------------------------------------------------------------
public class ConvexHullOptimization
{
long[] A;
long[] B;
int len;
int ptr;
public ConvexHullOptimization(int maxsize)
{
long[] A = new long[maxsize];
long[] B = new long[maxsize];
}
// a descends
public void AddLine(long a, long b)
{
// intersection of (A[len-2],B[len-2]) with (A[len-1],B[len-1]) must lie to the left of intersection of (A[len-1],B[len-1]) with (a,b)
while (len >= 2 && (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2])) len--;
A[len] = a;
B[len] = b;
len++;
}
// x ascends
public long MinValue(long x)
{
ptr = Math.Min(ptr, len - 1);
while (ptr + 1 < len && A[ptr + 1] * x + B[ptr + 1] <= A[ptr] * x + B[ptr]) ptr++;
return A[ptr] * x + B[ptr];
}
}
// -------------------------------------------------------------------------
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace algorithms.dp
{
// ----- Convex Hull Trick -------------------------------------------------
//
// To find minimum ( A[i] * x + B[i] ) for every x.
// -- Lines are added with DESCENDING A.
//
// ConvexHullTrick(int maxsize)
// void Add(long a, long b)
// long Query(long x)
// -------------------------------------------------------------------------
public class ConvexHullTrick
{
struct Line {
public long A;
public long B;
public Line(long a, long b)
{
A = a;
B = b;
}
public long Get(long x) { return A * x + B; }
public double Get(double x) { return A * x + B; }
}
Line[] hull;
int size;
public ConvexHullTrick(int maxsize)
{
hull = new Line[maxsize + 1];
size = 0;
}
bool IsBad(Line prev, Line curr, Line next)
{
return (double)(prev.B - curr.B) * (next.A - curr.A) >= (double)(curr.B - next.B) * (curr.A - prev.A);
}
public void Add(long a, long b)
{
Line newline = new Line(a, b);
hull[size++] = newline;
while (size > 2 && IsBad(hull[size - 3], hull[size - 2], hull[size - 1])) {
hull[size - 2] = newline;
size--;
}
}
public long Query(long x)
{
int l, r;
l = 0; r = size - 1;
while (l < r)
{
int m = (l + r) >> 1;
if (hull[m].Get(x) >= hull[m + 1].Get(x))
l = m + 1;
else
r = m;
}
if (l >= size) return long.MaxValue;
return hull[l].Get(x);
}
}
// -------------------------------------------------------------------------
}
using System;
namespace algorithms.dp
{
public static class EditDistance<T> where T : IEquatable<T>
{
// ---- -Edit Distance -------------------------------------------------
//
// Given two strings str1 and str2 and below operations that can
// performed on str1.Find minimum number of edits (operations)
// required to convert ‘str1’ into ‘str2’.
// a) Insert
// b) Remove
// c) Replace
//
// -- O(mn)
//
// T[] LCS(T[] A, T[] B)
// ---------------------------------------------------------------------
static int Min(int x, int y, int z)
{
return Math.Min(Math.Min(x, y), z);
}
public static int EditDist(T[] str1, T[] str2)
{
int m = str1.Length;
int n = str2.Length;
// Create a table to store results of subproblems
int[][] dp = new int[m + 1][];
for (int i = 0; i < m + 1; i++) dp[i] = new int[n + 1];
// Fill d[][] in bottom up manner
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
// If first string is empty, only option is to
// isnert all characters of second string
if (i == 0)
dp[i][j] = j; // Min. operations = j
// If second string is empty, only option is to
// remove all characters of second string
else if (j == 0)
dp[i][j] = i; // Min. operations = i
// If last characters are same, ignore last char
// and recur for remaining string
else if (str1[i - 1].Equals(str2[j - 1]))
dp[i][j] = dp[i - 1][j - 1];
// If last character are different, consider all
// possibilities and find minimum
else
dp[i][j] = 1 + Min(dp[i][j - 1], // Insert
dp[i - 1][j], // Remove
dp[i - 1][j - 1]); // Replace
}
}
return dp[m][n];
}
// ---------------------------------------------------------------------
}
}
using System;
namespace algorithms.dp
{
public static class Knapsack
{
// ----- Knapsack ------------------------------------------------------
// -- Given weights and values of n items, put these items in a knapsack
// -- of capacity W to get the maximum total value in the knapsack.
//
// -- v: values, w: weights, W: max weight capacity
//
// -- O(nW)
//
// -- knapsack 0-1
// -- restricts the number of copies of each kind of item to zero or one
//
// int ZeroOne(int[] v, int[] w, int W)
//
// -- unbounded (UKP)
// -- no upper bound on the number of copies of each kind of item
//
// int Unbounded(int[] v, int[] w, int W)
// int Unbounded2(int[] v, int[] w, int W)
// ---------------------------------------------------------------------
public static int ZeroOne(int[] v, int[] w, int W)
{
int n = v.Length;
int[] m = new int[W + 1];
for (int i = 0; i < n; i++)
for (int j = W; j >= 0; j--)
m[j] = j < w[i] ? m[j] : Math.Max(m[j], m[j - w[i]] + v[i]);
return m[W];
}
public static int Unbounded(int[] v, int[] w, int W)
{
int n = v.Length;
int[] m = new int[W + 1];
for (int i = 0; i < n; i++)
for (int j = w[i]; j <= W; j++)
m[j] = Math.Max(m[j], m[j - w[i]] + v[i]);
return m[W];
}
public static int Unbounded2(int[] v, int[] w, int W)
{
int n = v.Length;
int[] m = new int[W + 1];
for (int c = 1; c <= W; c++)
{
m[c] = m[c - 1];
for (int i = 0; i < n; i++)
if (w[i] <= c)
m[c] = Math.Max(m[c], m[c - w[i]] + v[i]);
}
return m[W];
}
// ---------------------------------------------------------------------
}
}
using System;
namespace algorithms.dp
{
public static class LongestCommonSubsequence<T> where T : IEquatable<T>
{
// ----- Longest Common Subsequence ------------------------------------
//
// -- O(mn)
//
// T[] LCS(T[] A, T[] B)
// ---------------------------------------------------------------------
public static T[] LCS(T[] X, T[] Y)
{
int m = X.Length;
int n = Y.Length;
int[][] L = new int[m + 1][];
for (int i = 0; i < m + 1; i++)
L[i] = new int[n + 1];
// Following steps build L[m+1][n+1] in bottom up fashion. Note
// that L[i][j] contains length of LCS of X[0..i-1] and Y[0..j-1]
for (int i = 0; i <= m; i++)
{
for (int j = 0; j <= n; j++)
{
if (i == 0 || j == 0)
L[i][j] = 0;
else if (X[i - 1].Equals(Y[j - 1]))
L[i][j] = L[i - 1][j - 1] + 1;
else
L[i][j] = Math.Max(L[i - 1][j], L[i][j - 1]);
}
}
// Following code is used to print LCS
int index = L[m][n];
// Create a character array to store the lcs string
T[] lcs = new T[index];
// Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int ix = m, jx = n;
while (ix > 0 && jx > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[ix - 1].Equals(Y[jx - 1]))
{
lcs[index - 1] = X[ix - 1]; // Put current character in result
ix--; jx--; index--; // reduce values of i, j and index
}
// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[ix - 1][jx] > L[ix][jx - 1])
ix--;
else
jx--;
}
return lcs;
}
// ---------------------------------------------------------------------
}
}
namespace algorithms.dp
{
public static class LongestIncreasingSubsequence
{
// ----- Longest Increasing Subsequence --------------------------------
//
// -- O(nlogn)
//
// int[] LIS(int[] A)
//
// non decreasing "if (A[increasingSub[mid]] <= A[i])" ?!
// ---------------------------------------------------------------------
public static int[] LIS(int[] A)
{
int[] parent = new int[A.Length]; //Tracking the predecessors/parents of elements of each subsequence.
int[] increasingSub = new int[A.Length + 1]; //Tracking ends of each increasing subsequence.
int length = 0; //Length of longest subsequence.
for (int i = 0; i < A.Length; i++)
{
//Binary search
int low = 1;
int high = length;
while (low <= high)
{
int mid = (low + high + 1) / 2;
if (A[increasingSub[mid]] < A[i])
low = mid + 1;
else
high = mid - 1;
}
int pos = low;
//update parent/previous element for LIS
parent[i] = increasingSub[pos - 1];
//Replace or append
increasingSub[pos] = i;
//Update the length of the longest subsequence.
if (pos > length) length = pos;
}
//Generate LIS by traversing parent array
int[] lis = new int[length];
int k = increasingSub[length];
for (int j = length - 1; j >= 0; j--)
{
lis[j] = A[k];
k = parent[k];
}
return lis;
}
// ---------------------------------------------------------------------
}
}